

/**
 * Created by L.jp
 * Description:
 * User: 86189
 * Date: 2023-04-06
 * Time: 23:34
 */
class ListNode {
    int val;
    ListNode next = null;
    
    public ListNode(int val) {
        this.val=val;
    }
}
public class Solution {
    public ListNode sortInList (ListNode head) {
        if(head==null || head.next==null){
            return head;
        }
        //快慢指针找中间节点，然后切分成两段，使用归并排序合并两个链表，因为每一段的链表不一定是顺序的，所以需要递归切分成每一段链表只有一个节点
        ListNode slow=head;
        ListNode fast=head.next.next;
        //找中间节点
        while (fast!=null && fast.next!=null){
            slow=slow.next;
            fast=fast.next.next;
        }
        //找到后先记录中间节点的下一个节点，作为右边一段链表的头节点
        ListNode tmp=slow.next;
        slow.next=null;
        //左边链表的的新的头结点
        ListNode left=sortInList(head);
        //右边链表的的新的头结点
        ListNode right=sortInList(tmp);
        //合并链表
        return merge(left,right);
    }
    public ListNode merge(ListNode h1,ListNode h2){
        if(h1==null){
            return h2;
        }
        if(h2==null){
            return h1;
        }
        ListNode head=new ListNode(0);
        ListNode cur=head;
        while (h1!=null && h2!=null){
            if(h1.val<h2.val) {
                cur.next = h1;
                h1 = h1.next;
            }else {
                cur.next=h2;
                h2=h2.next;
            }
            cur=cur.next;
        }
        cur.next=h1==null? h2:h1;
        return head.next;
    }
}
